
/*
 * Copyright (c) 2004 Apple Computer, Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 *
 * The contents of this file constitute Original Code as defined in and
 * are subject to the Apple Public Source License Version 1.1 (the
 * "License").  You may not use this file except in compliance with the
 * License.  Please obtain a copy of the License at
 * http://www.apple.com/publicsource and read it before using this file.
 *
 * This Original Code and all software distributed under the License are
 * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT.  Please see the
 * License for the specific language governing rights and limitations
 * under the License.
 *
 * @APPLE_LICENSE_HEADER_END@
 */

#include "hashtable_app.h"
#include "kernel.h"
//include <stdlib.h>
//#include <stdio.h>

HashTable* CreateHash(int ks)
{
	HashTable* result =  malloc(sizeof(HashTable));
//  printf("HT size: %d\n", sizeof(HashTable));	
   if (result == NULL) return NULL;
	
	result->fTable = NULL;
	result->fTableSize = 0;
	result->fNumEntries = 0;
	result->fKeyOffset = 0;
	result->fKeySize = ks;
		
	return result;
}
/*
void ReleaseHash(HashTable* hash)
{
	
	
	if (hash == NULL) return;
	
	if (hash->fTable != NULL)
	{
		for (int i = 0; i < hash->fTableSize; i++)
		{
			if (hs_entry* )(hash->fTable[i] != NULL)
				
		}
		free(hash->fTable);
	}
	
	free(hash);
}*/

unsigned int ComputeHash(HashTable* hash, unsigned int* key)
{      unsigned int hashOffset;
	
	unsigned char* keyPtr = (unsigned char*)key;
	int keySize = hash->fKeySize;
	
	if (key == NULL)
		return 0;
	
	hashOffset = 0;
	
	for (unsigned int i = 0; i < keySize; i++)
		hashOffset = (hashOffset ^ keyPtr[i] ^ (keyPtr[i] << 1) ^ (keyPtr[i] << 8)) + (keyPtr[i] << (keyPtr[i] % 7));
	hashOffset = hashOffset % (hash->fTableSize - 1);
    return hashOffset;
}

void ExpandTable(HashTable* hash)
{
	int i;
	int oldSize = hash->fTableSize;
	int newSize = oldSize * 2;
	if (newSize == 0)
		newSize = 128;
	hs_entry** newTable=calloc(4, newSize);
	if (newTable == NULL) return;
//	printf("sizeof hs entry: %d\n", sizeof(hs_entry));

	hash->fTableSize = newSize;

	if (hash->fTable != NULL)
	{ //printf("old table not null\n");
		for (i = 0; i < oldSize; i++)
		{
			if (hash->fTable[i] != NULL)
			{
				hs_entry* item = (hash->fTable[i]);
				int newHashOffset = ComputeHash(hash, &(item->key));
				while (newTable[newHashOffset] != NULL)
					newHashOffset = (newHashOffset + 1) % newSize;
				
				newTable[newHashOffset] = item;
			}
		}
		
		free(hash->fTable);
	}
       // printf("set up new table: %d\n", newSize);
	hash->fTable = newTable;
}
//1 if already exsited 0 otherwise
int AddToHash(HashTable* hash, unsigned int key, unsigned int val)
{
      

	unsigned int hashOffset;
	
	if (hash == NULL) return 1;
	
	if (hash->fNumEntries * 3 >= hash->fTableSize * 2)
		ExpandTable(hash);
	//printf("already expaned table\n");	
	if (hash->fNumEntries >= hash->fTableSize - 50) return 1;
	
	hashOffset = ComputeHash(hash, &key);
//	printf("hof %d\n", hashOffset);

	if (HashLookup(hash, &key) != NULL) return 1;
	
	 hs_entry* entry= malloc(sizeof(hs_entry));
        entry->key= key;
        entry->val= val;
  //        printf("data: %d\n", entry->key);
    //     printf("hashcode: %d\n", hashOffset);
        hash->fTable[hashOffset]=entry;
	
	
	hash->fNumEntries++;
      // printf("already looked up add one\n");
        return 0;
}
// data is key
hs_entry* HashLookup(HashTable* hash, unsigned int* data)
{      
	unsigned int hashOffset;
	
	if (hash == NULL) return NULL;
	
	if ( hash->fTable == NULL) return NULL;
	
	hashOffset = ComputeHash(hash, data);
      // printf("hashcode in lookup: %d\n", hashOffset);
       
       //printf("lookup hash addr: %d\n",*(int *) (hash));
	
       //printf("lookup addr: %d\n",*(int *) &(hash->fTable[0]));
      //if (*data != 0) printf("while 0: %d\n", (hash->fTable[0]->key));
	while (hash->fTable[hashOffset] != NULL) {
         //printf("in the while loop\n");
       //  printf("while key: %d\n", (hash->fTable[hashOffset]->key));
       if ((hash->fTable[hashOffset]->key) == *data){
         
             return ( hash->fTable[hashOffset]);}
        
       hashOffset = (hashOffset + 1) % hash->fTableSize;
        }
//printf("finish hashtable look-up\n");	
       return NULL;
	
}

void RemoveFromHash(HashTable* hash, unsigned int* key)
{
	unsigned int hashOffset;
	
	if (hash == NULL) return;
	
	if ( hash->fTable == NULL) return;
	
	hashOffset = ComputeHash(hash, key);
  //  printf("entry offset: %d\n", &(hash->fTable[hashOffset]));
	while( (hash->fTable[hashOffset] != NULL) && ((hash->fTable[hashOffset]->key) != *key))
		hashOffset = (hashOffset + 1) % hash->fTableSize;


	if (hash->fTable[hashOffset] != NULL)
	{
		
	 hash->fTable[hashOffset]=NULL;
		hash->fNumEntries--;
	}
	
	hashOffset = (hashOffset + 1) % hash->fTableSize;
	while (hash->fTable[hashOffset] != NULL)
	{
		unsigned int origOffset = ComputeHash(hash, &(hash->fTable[hashOffset]->key));
		if (origOffset != hashOffset)
		{
			// we need to shuffle this item
			hs_entry* itemToShuffle =hash->fTable[hashOffset];
		
			hash->fTable[hashOffset]=NULL;
			hash->fNumEntries--;
			AddToHash(hash, (itemToShuffle->key),(itemToShuffle ->val));
		}
		hashOffset = (hashOffset + 1) % hash->fTableSize;
	}
}

/*
int GetHashEntries(HashTable* hash, hs_entry* itemArray, long itemArraySize)
{
	int i;
	int numResults = 0;
	
	if (hash == NULL) return 0;
	
	if ( hash->fTable == NULL) return 0;
	
	for (i = 0; i < hash->fTableSize; i++)
	{
		if (hash->fTable[i] != NULL)
		{
			itemArray[numResults++] = hash->fTable[i];
			if (numResults >= itemArraySize) break;
		}
	}
	
	return numResults;
}
*/
